package map.mapadjoin.base;

import java.math.BigDecimal;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * 这里用的是邻接表来进行存储
 * @Auther Jun jie Yi
 * @Date 17:35 2021/8/16
 */
public class Graph<Type> {

    private CopyOnWriteArrayList<Vertex> vertices;//邻接表顶点集合

    private int numberEdges;//图的边数

    public Graph() {
        vertices = new CopyOnWriteArrayList<>();
        numberEdges = 0;
    }

    //图结点是否为空
    public boolean isEmpty() {
        return vertices.isEmpty();
    }

    //图结点的个数
    public int getNumberVertices() {
        return vertices.size();
    }

    //获取图的边数
    public int getNumberEdges() {
        return numberEdges;
    }

    //获取对应编号的结点对象
    public Vertex getValue(int i) {
        if (i >= 0 && i <= vertices.size()) {
            return vertices.get(i);
        } else {
            throw new IndexOutOfBoundsException();
        }
    }

    //查找该顶点在邻接表中的位置
    public int getVertexNumber(Vertex vertex) {
        return vertices.indexOf(vertex);
    }

    //插入一个结点
    public void addVertex(Type data) {
        if (data != null) {
            Vertex<Type> typeVertex = new Vertex<>();
            typeVertex.data = data;
            vertices.add(typeVertex);
        }
    }

    //移除一个结点
    public void removeVertex(int i) {
        if (i >= 0 && i <= vertices.size()) {
            vertices.remove(i);
        }
    }

    //添加一条边，如果是有方向的就是 v1 -> v2
    public void addEdge(int v1, int v2, BigDecimal weight) {
        if (v1 >= 0 && v1 <= vertices.size() && v2 >= 0 && v2 <= vertices.size() && v1 != v2 && weight != null) {
            //这里的链表采用尾插入法
            Vertex vertex = vertices.get(v1);
            EdgeNode edgeNode = vertex.adjList;
            if (edgeNode == null) {
                vertex.adjList = new EdgeNode();
                vertex.adjList.index = v2;
            } else {
                while (edgeNode.next != null) {
                    edgeNode = edgeNode.next;
                }
                EdgeNode edgeNode1 = new EdgeNode();
                edgeNode1.index = v2;
                edgeNode.next = edgeNode1;
            }
        }
    }

    //移除一条边，如果是有方向的就是 v1 -> v2
    public void removeEdge(int v1, int v2) {
        if (v1 >= 0 && v1 <= vertices.size() && v2 >= 0 && v2 <= vertices.size() && v1 != v2) {
            Vertex vertex = vertices.get(v1);
            EdgeNode r = vertex.adjList;
            if (r != null) {
                //先判断第一个结点
                if (r.index == v2) {
                    vertex.adjList = r.next;
                } else {
                    while (r.next != null) {
                        if (r.next.index == v2) {
                            r = r.next.next;
                        }
                    }
                }
            } else {
                throw new RuntimeException("无法删除空结点");
            }
        }
    }

    //显示图结构
    public void showGraph() {
        for (int i = 0; i < vertices.size(); i++) {
            EdgeNode adjList = vertices.get(i).adjList;
            StringBuilder str = new StringBuilder();
            while (adjList != null) {
                str.append(" -> " + adjList.index);
                adjList = adjList.next;
            }
            System.out.println(i + " " + vertices.get(i).data + str.append(" -> null"));
        }
    }
}
